from typing import List


class Solution:
    def maxStability(self, n: int, edges: List[List[int]], k: int) -> int:
        cnt = 0

        class UnionFind:
            def __init__(self, n):
                self.fa = [i for i in range(n)]

            def find(self, x):
                if self.fa[x] != x:
                    self.fa[x] = self.find(self.fa[x])
                return self.fa[x]

            def union(self, x, y):
                root_x = self.find(x)
                root_y = self.find(y)
                if root_x == root_y:
                    return False
                self.fa[root_y] = root_x
                return True

        uf = UnionFind(n)
        must = list(filter(lambda x: x[3], edges))
        must_build = []
        choice_build = []
        for u, v, s, must in must:
            if uf.union(u, v):
                cnt += 1
                must_build.append(s)
            else:
                return -1
        no_must = list(filter(lambda x: x[3] == 0, edges))
        no_must.sort(key=lambda x: x[2])
        while no_must:
            u, v, s, must = no_must.pop()
            if uf.union(u, v):
                cnt += 1
                choice_build.append(s)
        if cnt < n - 1: return -1
        choice_build.sort()
        for i in range(len(choice_build)):
            if i < k:
                choice_build[i] *= 2

        if not choice_build and must_build:
            return min(must_build)
        if not must_build and choice_build:
            return min(choice_build)

        return min(min(choice_build), min(must_build))


if __name__ == '__main__':
    s = Solution()
    r = s.maxStability(10, [[1, 3, 85282, 1], [2, 7, 15170, 1], [5, 8, 83816, 0], [0, 9, 6574, 1], [0, 6, 97906, 0],
                            [7, 9, 3, 0], [8, 9, 87261, 1], [3, 9, 21740, 0], [2, 6, 90270, 0], [3, 6, 47414, 1],
                            [6, 9, 57119, 0], [7, 8, 46995, 0]], 7)
    print(r)
